package com.captain.special.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/27 13:32
 */
public class 相交链表 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<>();
        ListNode tempA = headA;
        ListNode tempB = headB;
        //遍历两个链表
        while (tempA != null && tempB != null) {
            if (visited.contains(tempA)) {
                return tempA;
            }
            visited.add(tempA);
            if (visited.contains(tempB)) {
                return tempB;
            }
            visited.add(tempB);

            tempA = tempA.next;
            tempB = tempB.next;
        }
        //如果存在一个链表不为空
        if (tempA == null) {
            while (tempB != null) {
                if (visited.contains(tempB)) {
                    return tempB;
                }
                tempB = tempB.next;
            }
        } else {
            while (tempA != null) {
                if (visited.contains(tempA)) {
                    return tempA;
                }
                tempA = tempA.next;
            }
        }
        return null;
    }
}
